#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

#ifdef _MSC_VER
#define CPP_STANDARD _MSVC_LANG
#else
#define CPP_STANDARD __cplusplus
#endif
#if CPP_STANDARD >= 201402L
#define CONSTEXPR_IF_CPP14 constexpr
#else
#define CONSTEXPR_IF_CPP14
#endif
namespace std {
    namespace my_bit_ops {
        static constexpr int s32[32] = {31, 0, 1, 5, 2, 10, 6, 15, 3, 13, 11, 20, 7, 22, 16, 25, 30, 4, 9, 14, 12, 19, 21, 24, 29, 8, 18, 23, 28, 17, 27, 26};
        static constexpr int s64[64] = {63, 0, 1, 6, 2, 12, 7, 18, 3, 24, 13, 27, 8, 33, 19, 39, 4, 16, 25, 37, 14, 45, 28, 47, 9, 30, 34, 53, 20, 49, 40, 56, 62, 5, 11, 17, 23, 26, 32, 38, 15, 36, 44, 46, 29, 52, 48, 55, 61, 10, 22, 31, 35, 43, 51, 54, 60, 21, 42, 50, 59, 41, 58, 57};
        static constexpr int s256[256] = {8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
        static constexpr int ctz32(uint32_t x) noexcept { return s32[(x & -x) * 0b00001000110010100111010110111110 >> 27]; }
        static constexpr int ctz64(uint64_t x) noexcept { return s64[(x & -x) * 0b0000010000110001010001110010010110011010011110101011101101111110 >> 58]; }
        static constexpr int clz8(uint32_t x) noexcept { return s256[x]; }
        static constexpr int clz16(uint32_t x) noexcept { return x >> 8 ? clz8(x >> 8) : 8 + clz8(x); }
        static constexpr int clz32(uint32_t x) noexcept { return x >> 16 ? clz16(x >> 16) : 16 + clz16(x); }
        static constexpr int clz64(uint64_t x) noexcept { return x >> 32 ? clz32(x >> 32) : 32 + clz32(x); }
        static constexpr uint32_t f1_32(uint32_t x) noexcept { return x - ((x >> 1) & 0x55555555); }
        static constexpr uint32_t f2_32(uint32_t x) noexcept { return (x & 0x33333333) + ((x >> 2) & 0x33333333); }
        static constexpr int f3_32(uint32_t x) noexcept { return (x + (x >> 4) & 0x0f0f0f0f) * 0x01010101 >> 24; }
        static constexpr int popcnt32(uint32_t x) noexcept { return f3_32(f2_32(f1_32(x))); }
        static constexpr uint64_t f1_64(uint64_t x) noexcept { return x - ((x >> 1) & 0x5555555555555555); }
        static constexpr uint64_t f2_64(uint64_t x) noexcept { return (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); }
        static constexpr int f3_64(uint64_t x) noexcept { return (x + (x >> 4) & 0x0f0f0f0f0f0f0f0f) * 0x0101010101010101 >> 56; }
        static constexpr int popcnt64(uint64_t x) noexcept { return f3_64(f2_64(f1_64(x))); }
        constexpr uint32_t bit_ceil_msvc_32(uint32_t x) noexcept { return x ? uint32_t(1) << (32 - clz32(x - 1)) : 1; }
        constexpr uint64_t bit_ceil_msvc_64(uint64_t x) noexcept { return x ? uint64_t(1) << (64 - clz64(x - 1)) : 1; }
        template <typename Tp>
        constexpr Tp bit_ceil_msvc(Tp x) noexcept { return sizeof(Tp) == 4 ? bit_ceil_msvc_32(x) : bit_ceil_msvc_64(x); }
        constexpr uint32_t bit_floor_msvc_32(uint32_t x) noexcept { return x ? uint32_t(1) << (31 - clz32(x)) : 0; }
        constexpr uint64_t bit_floor_msvc_64(uint64_t x) noexcept { return x ? uint64_t(1) << (63 - clz64(x)) : 0; }
        template <typename Tp>
        constexpr Tp bit_floor_msvc(Tp x) noexcept { return sizeof(Tp) == 4 ? bit_floor_msvc_32(x) : bit_floor_msvc_64(x); }
        constexpr uint32_t bit_width_msvc_32(uint32_t x) noexcept { return 32 - clz32(x); }
        constexpr uint64_t bit_width_msvc_64(uint64_t x) noexcept { return 64 - clz64(x); }
        template <typename Tp>
        constexpr Tp bit_width_msvc(Tp x) noexcept { return sizeof(Tp) == 4 ? bit_width_msvc_32(x) : bit_width_msvc_64(x); }
        constexpr int countl_zero_msvc_32(uint32_t x) noexcept { return x ? clz32(x) : 32; }
        constexpr int countl_zero_msvc_64(uint64_t x) noexcept { return x ? clz64(x) : 64; }
        template <typename Tp>
        constexpr int countl_zero_msvc(Tp x) noexcept { return sizeof(Tp) == 4 ? countl_zero_msvc_32(x) : countl_zero_msvc_64(x); }
        constexpr int countr_zero_msvc_32(uint32_t x) noexcept { return x ? ctz32(x) : 32; }
        constexpr int countr_zero_msvc_64(uint64_t x) noexcept { return x ? ctz64(x) : 64; }
        template <typename Tp>
        constexpr int countr_zero_msvc(Tp x) noexcept { return sizeof(Tp) == 4 ? countr_zero_msvc_32(x) : countr_zero_msvc_64(x); }
        template <typename Tp>
        constexpr int popcount_msvc(Tp x) noexcept { return sizeof(Tp) == 4 ? popcnt32(x) : popcnt64(x); }
#ifdef _MSC_VER
        template <typename Tp>
        constexpr Tp bit_ceil(Tp x) noexcept { return bit_ceil_msvc(x); }
        template <typename Tp>
        constexpr Tp bit_floor(Tp x) noexcept { return bit_floor_msvc(x); }
        template <typename Tp>
        constexpr Tp bit_width(Tp x) noexcept { return bit_width_msvc(x); }
        template <typename Tp>
        constexpr int countl_zero(Tp x) noexcept { return countl_zero_msvc(x); }
        template <typename Tp>
        constexpr int countr_zero(Tp x) noexcept { return countr_zero_msvc(x); }
        template <typename Tp>
        constexpr int popcount(Tp x) noexcept { return popcount_msvc(x); }
#else
        constexpr uint32_t bit_ceil_32(uint32_t x) noexcept { return x > 1 ? uint32_t(1) << (32 - __builtin_clz(x - 1)) : 1; }
        constexpr uint64_t bit_ceil_64(uint64_t x) noexcept { return x > 1 ? uint64_t(1) << (64 - __builtin_clzll(x - 1)) : 1; }
        template <typename Tp>
        constexpr Tp bit_ceil(Tp x) noexcept { return sizeof(Tp) == 4 ? bit_ceil_32(x) : bit_ceil_64(x); }
        constexpr uint32_t bit_floor_32(uint32_t x) noexcept { return x ? uint32_t(1) << (31 - __builtin_clz(x)) : 0; }
        constexpr uint64_t bit_floor_64(uint64_t x) noexcept { return x ? uint64_t(1) << (63 - __builtin_clzll(x)) : 0; }
        template <typename Tp>
        constexpr Tp bit_floor(Tp x) noexcept { return sizeof(Tp) == 4 ? bit_floor_32(x) : bit_floor_64(x); }
        constexpr uint32_t bit_width_32(uint32_t x) noexcept { return x ? 32 - __builtin_clz(x) : 0; }
        constexpr uint64_t bit_width_64(uint64_t x) noexcept { return x ? 64 - __builtin_clzll(x) : 0; }
        template <typename Tp>
        constexpr Tp bit_width(Tp x) noexcept { return sizeof(Tp) == 4 ? bit_width_32(x) : bit_width_64(x); }
        constexpr int countl_zero_32(uint32_t x) noexcept { return x ? __builtin_clz(x) : 32; }
        constexpr int countl_zero_64(uint64_t x) noexcept { return x ? __builtin_clzll(x) : 64; }
        template <typename Tp>
        constexpr int countl_zero(Tp x) noexcept { return sizeof(Tp) == 4 ? countl_zero_32(x) : countl_zero_64(x); }
        constexpr int countr_zero_32(uint32_t x) noexcept { return x ? __builtin_ctz(x) : 32; }
        constexpr int countr_zero_64(uint64_t x) noexcept { return x ? __builtin_ctzll(x) : 64; }
        template <typename Tp>
        constexpr int countr_zero(Tp x) noexcept { return sizeof(Tp) == 4 ? countr_zero_32(x) : countr_zero_64(x); }
        template <typename Tp>
        constexpr int popcount(Tp x) noexcept { return sizeof(Tp) == 4 ? __builtin_popcount(x) : __builtin_popcountll(x); }
#endif
    }
#ifndef __cpp_lib_bitops
    using my_bit_ops::bit_ceil;
    using my_bit_ops::bit_floor;
    using my_bit_ops::bit_width;
    using my_bit_ops::countl_zero;
    using my_bit_ops::countr_zero;
    using my_bit_ops::popcount;
#endif
}

namespace OY {
    namespace DIGITDP {
        using size_type = uint32_t;
        template <uint32_t Base>
        struct StaticIntegerString {
            std::vector<uint32_t> m_str;
            static constexpr uint32_t base() { return Base; }
            StaticIntegerString() = default;
            StaticIntegerString(uint64_t val) {
                do m_str.push_back(val % Base), val /= Base;
                while (val);
            }
            size_type size() const { return m_str.size(); }
            void assign(size_type n) { m_str.assign(n, 0); }
            uint32_t get(size_type i) const { return m_str[i]; }
            void set(size_type i, uint32_t val) { m_str[i] = val; }
            void push_high(uint32_t val) { m_str.push_back(val); }
            void pop_high() { m_str.pop_back(); }
            operator uint64_t() const {
                uint64_t val = 0;
                for (size_type i = size() - 1; ~i; i--) val = val * Base + get(i);
                return val;
            }
        };
        template <>
        struct StaticIntegerString<2> {
            std::vector<uint64_t> m_str;
            size_type m_size;
            static constexpr uint32_t base() { return 2; }
            StaticIntegerString() = default;
            StaticIntegerString(uint64_t val) {
                m_str.assign(1, val);
                m_size = val ? std::bit_width(val) : 1;
            }
            StaticIntegerString(std::string str) {
                size_type i = str.find('1');
                if (i == size_type(std::string::npos))
                    assign(1);
                else {
                    assign(str.size() - i);
                    for (size_type j = str.size() - 1; j != i - 1; j--) set(str.size() - 1 - j, str[j] - '0');
                }
            }
            explicit StaticIntegerString(const char *str) : StaticIntegerString(std::string(str)) {}
            size_type size() const { return m_size; }
            void assign(size_type n) { m_str.assign((n + 63) >> 6, 0), m_size = n; }
            uint32_t get(size_type i) const { return m_str[i >> 6] >> (i & 63) & 1; }
            void set(size_type i, uint32_t val) {
                if (val)
                    m_str[i >> 6] |= uint64_t(1) << (i & 63);
                else
                    m_str[i >> 6] &= ~(uint64_t(1) << (i & 63));
            }
            void push_high(uint32_t val) {
                if (!(m_size++ & 63))
                    m_str.push_back(val);
                else
                    set(m_size - 1, val);
            }
            void pop_high() {
                if (!(--m_size & 63))
                    m_str.pop_back();
                else
                    set(m_size, 0);
            }
            operator std::string() const {
                std::string str(m_size, '0');
                for (size_type i = 0; i != m_size; i++) str[i] = '0' + get(m_size - 1 - i);
                return str;
            }
            operator uint64_t() const { return m_str[0]; }
        };
        template <>
        struct StaticIntegerString<10> {
            std::string m_str;
            static constexpr uint32_t base() { return 10; }
            StaticIntegerString() = default;
            StaticIntegerString(uint64_t val) {
                do m_str += '0' + val % 10, val /= 10;
                while (val);
            }
            StaticIntegerString(std::string str) : m_str(str.rbegin(), str.rend()) {}
            explicit StaticIntegerString(const char *str) : StaticIntegerString(std::string(str)) {}
            size_type size() const { return m_str.size(); }
            void assign(size_type n) { m_str.assign(n, '0'); }
            uint32_t get(size_type i) const { return m_str[i] - '0'; }
            void set(size_type i, uint32_t val) { m_str[i] = '0' + val; }
            void push_high(uint32_t val) { m_str += '0' + val; }
            void pop_high() { m_str.pop_back(); }
            operator std::string() const { return std::string(m_str.rbegin(), m_str.rend()); }
            operator uint64_t() const {
                uint64_t val = 0;
                for (size_type i = size() - 1; ~i; i--) val = val * 10 + get(i);
                return val;
            }
        };
        struct DynamicIntegerString {
            std::vector<uint32_t> m_str;
            static uint32_t s_base;
            static void set_base(uint32_t base) { s_base = base; }
            static uint32_t base() { return s_base; }
            DynamicIntegerString() = default;
            DynamicIntegerString(uint64_t val) {
                do m_str.push_back(val % s_base), val /= s_base;
                while (val);
            }
            size_type size() const { return m_str.size(); }
            void assign(size_type n) { m_str.assign(n, 0); }
            uint32_t get(size_type i) const { return m_str[i]; }
            void set(size_type i, uint32_t val) { m_str[i] = val; }
            void push_high(uint32_t val) { m_str.push_back(val); }
            void pop_high() { m_str.pop_back(); }
            operator uint64_t() const {
                uint64_t val = 0;
                for (size_type i = size() - 1; ~i; i--) val = val * s_base + get(i);
                return val;
            }
        };
        uint32_t DynamicIntegerString::s_base;
        template <typename Ostream, uint32_t Base>
        Ostream &operator<<(Ostream &out, const StaticIntegerString<Base> &str) {
            for (size_type i = str.size() - 1; ~i; i--) out << str.get(i);
            return out;
        }
        template <typename Ostream>
        Ostream &operator<<(Ostream &out, const DynamicIntegerString &str) {
            for (size_type i = str.size() - 1; ~i; i--) out << str.get(i);
            return out;
        }
        template <typename IntStr>
        IntStr prev_number(IntStr s) {
            size_type n = s.size(), i = 0;
            while (i != n && !s.get(i)) s.set(i++, IntStr::base() - 1);
            s.set(i, s.get(i) - 1);
            if (n > 1 && i == n - 1 && !s.get(i)) s.pop_high();
            return s;
        }
        template <typename IntStr>
        IntStr next_number(IntStr s) {
            size_type n = s.size(), i = 0;
            while (i != n && s.get(i) == IntStr::base() - 1) s.set(i++, 0);
            if (i == n)
                s.push_high(1);
            else
                s.set(i, s.get(i) + 1);
            return s;
        }
        template <typename Tp, typename IntStr, bool Trace>
        struct Tracer {};
        template <typename Tp, typename IntStr>
        class Tracer<Tp, IntStr, true> {
        protected:
            std::vector<std::vector<std::vector<std::pair<uint32_t, uint32_t>>>> m_from;
            IntStr m_str;
            void init(uint32_t state_count, IntStr number) {
                m_str = number;
                m_from.assign(number.size(), std::vector<std::vector<std::pair<uint32_t, uint32_t>>>(state_count));
            }
            void add_trace(uint32_t state, uint32_t prev_state, size_type prev_len, uint32_t c) { m_from[prev_len][state].emplace_back(prev_state, c); }
            template <typename Callback>
            void _dfs1(size_type idx, uint32_t state, bool equal, IntStr &str, Callback &&call) {
                if (!~idx)
                    call(str);
                else {
                    for (auto &prev_state_c : m_from[idx][state]) {
                        auto prev_state = prev_state_c.first;
                        auto c = prev_state_c.second;
                        if (equal && c > m_str.get(idx)) continue;
                        if (!c && idx == str.size() - 1 && idx) continue;
                        str.set(idx, c);
                        _dfs1(idx - 1, prev_state, equal && c == m_str.get(idx), str, call);
                    }
                }
            }
            template <typename Callback>
            void _dfs2(size_type idx, uint32_t state, int comp, IntStr &str, Callback &&call) {
                if (!~idx) {
                    if (str.size() < m_str.size() || comp != 1) call(str);
                } else {
                    uint32_t cur = m_str.get(str.size() - 1 - idx);
                    for (auto &prev_state_c : m_from[idx][state]) {
                        auto prev_state = prev_state_c.first;
                        auto c = prev_state_c.second;
                        if (!idx && !c) continue;
                        str.set(str.size() - 1 - idx, c);
                        _dfs2(idx - 1, prev_state, c > cur ? 1 : (c < cur ? -1 : comp), str, call);
                    }
                }
            }
            template <typename Callback>
            void enumerate1(uint32_t state, size_type len, Callback &&call) {
                IntStr str;
                str.assign(len);
                _dfs1(len - 1, state, len == m_str.size(), str, call);
            }
            template <typename Callback>
            void enumerate2(uint32_t state, size_type len, Callback &&call) {
                IntStr str;
                str.assign(len);
                _dfs2(len - 1, state, 0, str, call);
            }
        };
        template <typename Tp, typename IntStr, bool Trace = false>
        struct AppendHighSolver : Tracer<Tp, IntStr, Trace> {
            using base_type = Tracer<Tp, IntStr, Trace>;
            size_type n;
            std::vector<std::array<Tp, 2>> dp, dp2;
            template <typename Transfer, typename PlusCallback, typename MinusCallback>
            void _solve_callback(IntStr number, uint32_t state_count, Transfer &&transfer, PlusCallback &&plus, MinusCallback &&minus) {
                n = number.size(), dp.assign(state_count, {}), dp2.assign(state_count, {});
                if constexpr (Trace) base_type::init(state_count, number);
                for (uint32_t c = 0; c != IntStr::base(); c++) {
                    uint32_t state = transfer(-1, 0, c);
                    if (!~state) continue;
                    dp[state][c > number.get(0)]++;
                    if constexpr (Trace) base_type::add_trace(state, -1, 0, c);
                    if (c) continue;
                    if (n - 1)
                        for (uint32_t state = 0; state != state_count; state++) minus(dp[state][0] + dp[state][1], state, 1);
                    else
                        for (uint32_t state = 0; state != state_count; state++) minus(dp[state][0], state, 1);
                }
                if (n - 1)
                    for (uint32_t state = 0; state != state_count; state++) plus(dp[state][0] + dp[state][1], state, 1);
                else
                    for (uint32_t state = 0; state != state_count; state++) plus(dp[state][0], state, 1);
                for (size_type i = 1; i != n; i++) {
                    uint32_t cur = number.get(i);
                    dp.swap(dp2);
                    dp.assign(state_count, {});
                    for (uint32_t c = 0; c != IntStr::base(); c++) {
                        for (uint32_t state = 0; state != state_count; state++)
                            if (dp2[state][0] || dp2[state][1]) {
                                uint32_t state2 = transfer(state, i, c);
                                if (~state2) {
                                    dp[state2][c > cur] += dp2[state][0], dp[state2][c >= cur] += dp2[state][1];
                                    if constexpr (Trace) base_type::add_trace(state2, state, i, c);
                                }
                            }
                        if (!c)
                            if (i + 1 < n)
                                for (uint32_t state = 0; state != state_count; state++) minus(dp[state][0] + dp[state][1], state, i + 1);
                            else
                                for (uint32_t state = 0; state != state_count; state++) minus(dp[state][0], state, i + 1);
                    }
                    if (i + 1 < n)
                        for (uint32_t state = 0; state != state_count; state++) plus(dp[state][0] + dp[state][1], state, i + 1);
                    else
                        for (uint32_t state = 0; state != state_count; state++) plus(dp[state][0], state, i + 1);
                }
            }
            template <typename Transfer, typename ValueMapping>
            Tp solve(IntStr number, uint32_t state_count, Transfer &&transfer, ValueMapping &&mapping) {
                Tp ans{};
                auto plus = [&](Tp cnt, uint32_t state, size_type len) { ans += cnt * mapping(state, len); };
                auto minus = [&](Tp cnt, uint32_t state, size_type len) { ans -= cnt * mapping(state, len); };
                _solve_callback(std::move(number), state_count, transfer, plus, minus);
                return ans;
            }
            template <typename ValueMapping, typename Callback>
            void enumerate(ValueMapping &&mapping, Callback &&call) {
                static_assert(Trace, "Trace Must Be True");
                uint32_t state_count = dp.size();
                for (size_type len = 1; len <= this->m_str.size(); len++)
                    for (uint32_t state = 0; state != state_count; state++)
                        if (this->m_from[len - 1][state].size() && mapping(state, len)) base_type::enumerate1(state, len, call);
            }
        };
        using IntStr2 = StaticIntegerString<2>;
        using IntStr10 = StaticIntegerString<10>;
        IntStr2 prev_number_base2(std::string s) { return prev_number(IntStr2(std::move(s))); }
        IntStr2 next_number_base2(std::string s) { return next_number(IntStr2(std::move(s))); }
        IntStr10 prev_number_base10(std::string s) { return prev_number(IntStr10(std::move(s))); }
        IntStr10 next_number_base10(std::string s) { return next_number(IntStr10(std::move(s))); }
    }
}

template
<
    typename AnswerType = long long,            // 结果类型
    typename ParamType = OY::DIGITDP::IntStr10  // 参数类型
>
struct LowToHighDPer {

public:// 求[1, n]之间的答案
AnswerType solve(ParamType n){
    return Solver.solve(n, this->state_count, this->Transfer, this->Mapping);
}

public: // 求[a, b]之间的答案，为了适配，不使用a - 1
AnswerType solve(ParamType a, ParamType b){
    return this->solve(b) - this->solve(prev_number(a));
}

/**
 * @param stateCout 不同状态的数量，必须是字面值，否则析构的时候会有df
 * @param transfer 给定老状态、长度、当前添加的数字c，返回新状态，c是添加在低位
 * @param mapping 给定终态和长度，计算对答案的贡献
 */
LowToHighDPer
(
    uint32_t stateCount, 
    std::function<uint32_t(uint32_t, uint32_t, uint32_t)> transfer, 
    std::function<AnswerType(uint32_t, uint32_t)> mapping
):Solver(), state_count(stateCount), Transfer(transfer), Mapping(mapping){}


OY::DIGITDP::AppendHighSolver<AnswerType, ParamType> Solver;
std::function<uint32_t(uint32_t, uint32_t, uint32_t)> Transfer;
std::function<AnswerType(uint32_t, uint32_t)> Mapping;
const uint32_t state_count;

};